package bTree.LeetCode;

import java.util.HashMap;
import java.util.LinkedList;

public class LRU缓存 {

    class DoubleLinked{
        DoubleLinked pre;
        DoubleLinked pro;
        int key;
        int val;
    }
    DoubleLinked head,tail;
    HashMap<Integer,DoubleLinked>hashMap=new HashMap<>();
    public final int capacity;

    public LRU缓存(int capacity) {
        this.capacity = capacity;
        head=new DoubleLinked();
        tail=new DoubleLinked();
        head.pro=tail;
        tail.pre=head;

    }

    public int get(int key) {
        if (!hashMap.containsKey(key)){
            return -1;
        }else {
            DoubleLinked doubleLinked = hashMap.get(key);
            //1.删除节点位置
            removeNode(doubleLinked);
            //2.在头部新增
            addHead(doubleLinked);
            return doubleLinked.val;
        }
    }

    private void addHead(DoubleLinked doubleLinked) {
        doubleLinked.pre=head;
        doubleLinked.pro=head.pro;
        head.pro.pre=doubleLinked;
        head.pro=doubleLinked;
    }

    /**
     * 删除节点位置
     * @param doubleLinked
     */
    private void removeNode(DoubleLinked doubleLinked) {
        doubleLinked.pre.pro=doubleLinked.pro;
        doubleLinked.pro.pre=doubleLinked.pre;
    }


    public void put(int key, int value) {
        DoubleLinked doubleLinked = hashMap.get(key);
        if (hashMap.containsKey(key)){
            doubleLinked.val=value;
            //1.删除节点
            removeNode(doubleLinked);
            //2.在头部新增
            addHead(doubleLinked);
        }else {
            DoubleLinked doubleLinked1 = new DoubleLinked();
            doubleLinked1.val=value;
            doubleLinked1.key=key;
            if (hashMap.size()==capacity){
                removeTail();
                //2.在头部新增
                addHead(doubleLinked1);
            }else {
                //2.在头部新增
                addHead(doubleLinked1);
            }
            hashMap.put(key, doubleLinked1);
        }
    }

    private void removeTail() {
        hashMap.remove(tail.pre.key);
        tail.pre.pre.pro=tail;
        tail.pre=tail.pre.pre;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */